package offer;

import binaryTree.basic.TreeNode;

import java.util.HashMap;

public class Offer07 {

    HashMap<Integer, Integer> valtoIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valtoIndex.put(inorder[i], i);
        }

        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        int rootVal=preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        Integer index = valtoIndex.get(rootVal);
        int leftNodeNums=index-inStart;
        root.left=build(preorder,preStart+1,preStart+leftNodeNums,inorder,inStart,index-1);
        root.right=build(preorder,preStart+leftNodeNums+1,preEnd,inorder,index+1,inEnd);

        return root;




    }


}
